package binaryTree;

import java.util.HashMap;
import java.util.Map;

public class BulidTree {
	public Map<Integer,Integer> hash=new HashMap<>();
	public TreeNode dfs(int[] preorder,int l1,int r1,int[] inorder,int l2,int r2) {
		if(l1>r1) { //l1>r1 => 无效区间
			return null;
		}
		
		TreeNode head=new TreeNode(preorder[l1]);
		if(l1==r1) {      //l1==r1，说明区间内只有1个节点，直接返回
			return head;
		}
		
		int k=hash.get(preorder[l1]); //查找头结点在中序数组中的位置
		
		head.left=dfs(preorder,l1+1,l1+k-l2,inorder,l2,k-1);
		head.right=dfs(preorder,l1+k-l2+1,r1,inorder,k+1,r2);
		return head;
	}
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		if(preorder==null||inorder==null||preorder.length!=inorder.length) {
			return null;
		}
        for(int i=0;i<inorder.length;i++) {
        	hash.put(inorder[i],i);
        }
        return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

}
